package com.minibase.exec.logexec;

import java.lang.reflect.Field;
import java.util.AbstractMap;
import java.util.Objects;
import java.util.Set;
import java.util.concurrent.ThreadLocalRandom;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.Function;

import sun.misc.Unsafe;

/**
 * @author zouzhiwen
 * @date 2022/1/6 14:23
 */
public class MiniSkipListMap<K, V> extends AbstractMap<K, V> {

    private volatile HeadIndex<K, V> head;

    private static final Object BASE_HEADER = new Object();

    public MiniSkipListMap() {
        head = new HeadIndex<>(new Node<>(null, BASE_HEADER, null), null, null, 1);
    }

    public V put(K key, V value, boolean onlyIfAbsent) {
        Objects.requireNonNull(value);
        return doPut(key, value, onlyIfAbsent);
    }

    public V get(Object key) {
        return doGet(key);
    }

    public V remove(Object key) {
        Objects.requireNonNull(key);
        return doRemove(key, null);
    }


    public Set<Entry<K, V>> entrySet() {
        //TODO entrySet
        return null;
    }


    public V getOrDefault(Object key, V defaultValue) {
        V v;
        return (v = doGet(key)) == null ? defaultValue : v;
    }


    public void forEach(BiConsumer<? super K, ? super V> action) {
        Objects.requireNonNull(action);
        for (Node<K, V> base = findFirst(); base != null; base = base.next) {
            V v;
            if ((v = base.getValidValue()) != null) {
                action.accept(base.key, v);
            }
        }
    }


    public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
        Objects.requireNonNull(function);
        for (Node<K, V> base = findFirst(); base != null; base = base.next) {
            V v;
            while ((v = base.getValidValue()) != null) {
                V r = function.apply(base.key, v);
                Objects.requireNonNull(r);
                if (base.casValue(v, r))
                    break;
            }
        }
    }


    public V putIfAbsent(K key, V value) {
        Objects.requireNonNull(value);
        return doPut(key, value, true);
    }


    public boolean remove(Object key, Object value) {
        Objects.requireNonNull(key);
        return value != null && doRemove(key, value) != null;
    }


    public boolean replace(K key, V oldValue, V newValue) {
        Objects.requireNonNull(key);
        Objects.requireNonNull(oldValue);
        Objects.requireNonNull(newValue);
        for(;;) {
            Node<K, V> find; Object v;
            if ((find = findNode(key)) == null) {
                return false;
            }
            if ((v = find.value) != null) {
                if (!oldValue.equals(v)) {
                    return false;
                }
                if (find.casValue(oldValue, newValue)) {
                    return true;
                }
            }
        }
    }


    public V replace(K key, V value) {
        Objects.requireNonNull(key);
        Objects.requireNonNull(value);
        for(;;) {
            Node<K, V> find; Object v;
            if ((find = findNode(key)) == null) {
                return null;
            }
            if ((v = find.value) != null && find.casValue(v, value)) {
                @SuppressWarnings("unchecked")
                V vv = (V) v;
                return vv;
            }
        }
    }

    /**
     * 不存在才put
     */
    public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
        Objects.requireNonNull(key);
        Objects.requireNonNull(mappingFunction);
        V v, p, r;
        if (((v = doGet(key)) == null)
                && ((r = mappingFunction.apply(key)) != null)) {
                v = (p = doPut(key, r, true)) == null ? r : p;
        }
        return v;
    }

    /**
     * 存在才put
     */
    public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
        Objects.requireNonNull(key);
        Objects.requireNonNull(remappingFunction);
        Node<K, V> find; Object v;
        while ((find = findNode(key)) != null) {
            if ((v = find.value) != null) {
                V vv = (V) v;
                V r = remappingFunction.apply(key, vv);
                if (r != null) {
                    if (find.casValue(v, r))
                        return r;
                }
                else if (doRemove(key, vv) != null) {
                    break;
                }
            }
        }
        return null;
    }

    /**
     * 根据是否存在填不同值
     * ex:
     *  (k,v)->{
     *      if(v == null) {
     *          v = 1;
     *      }else {
     *          v += 1;
     *      }
     *      return v;
     *  }
     *  ==================
     *  v = map.get(key)
     *  if (v == null) {
     *      v = 1;
     *  }else {
     *      v += 1;
     *  }
     *  map.put(k,v);
     */
    public V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
        Objects.requireNonNull(key);
        Objects.requireNonNull(remappingFunction);
        for (;;) {
            Node<K, V> find;
            Object v;
            V r;
            if ((find = findNode(key)) == null) {
                if ((r = remappingFunction.apply(key, null)) == null)
                    break;
                if (doPut(key, r, true) == null)
                    return r;
            } else if ((v = find.value) != null) {
                V vv = (V) v;
                if ((r = remappingFunction.apply(key, vv)) != null) {
                    if (find.casValue(vv, r)) {
                        return r;
                    }
                } else if (doRemove(key, vv) != null) {
                    break;
                }
            }
        }
        return null;
    }


    /**
     * 当map中不存在指定的key时，便将传入的value设置为key的值，当key存在值时，执行一个方法该方法接收key的旧值和传入的value，执行自定义的方法返回最终结果设置为key的值
     */
    public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
        Objects.requireNonNull(key);
        Objects.requireNonNull(value);
        Objects.requireNonNull(remappingFunction);
        for(;;) {
            Node<K, V> find; Object v;
            if ((find = findNode(key)) == null) {
                if (doPut(key, value, true) == null) {
                    return value;
                }
            } else if ((v = find.value) != null) {
                V vv = (V) v;
                V r;
                if ((r = remappingFunction.apply(vv, value)) != null) {
                    if (find.casValue(vv, r)) {
                        return r;
                    }
                } else if (doRemove(key, vv) != null) {
                    break;
                }
            }
        }
        return null;
    }

    public boolean isEmpty() {
        return findFirst() == null;
    }

    private Node<K, V> findFirst() {
        for (Node<K,V> b, n;;) {
            if ((n = (b = head.node).next) == null)
                return null;
            if (n.value != null)
                return n;
            n.helpDelete(b, n.next);
        }
    }

    /**
     * 删除一个节点的步骤：
     * 1.用findPredecessor在底层找到删除节点的前驱节点
     * 2.从前驱节点遍历找到目标节点
     * 3.没有找到目标节点,退出,返回null
     * 4.找到元素后，先通过n.casValue(v,null)将目标节点的值置为null
     * 5.再删除元素的后面添加一个marker元素
     * 6.将前驱节点指向目标元素的后继节点
     * 7.删除目标节点的上层索引
     * 8.判断是否降级
     *
     * 为什么删除节点时不直接将前驱节点的next指向后继节点，而要通过4,5,6三个步骤
     * 举个例子：8->9->12
     * 如果在删除9时,有其他线程put了一个10,这样10就会被丢弃
     * 如果改为8->9->marker->12
     * 如果put10的线程先执行,在添加marker时就会失败,此时会通过findNode()中的helpDelete()方法做2步操作：
     *      1、先给9的next加上marker节点,marker是一个value为本身的节点,next即为10
     *      2、将8的next指向marker的next,即为10
     * 如果添加marker的操作先执行,则put中的casNext()操作会失败,重新走put流程,进入helpDelete()中
     */
    private V doRemove(Object key, Object value) {
        out:
        for (;;) {
            for (Node<K, V> base = findPredecessor(key), n = base.next; ; ) {
                if (n == null)
                    break out;
                Object v;
                int c;
                Node<K, V> f = n.next;
                if (n != base.next) { //读不一致
                    break;
                }
                if ((v = n.value) == null) { //n节点已被删
                    n.helpDelete(base, f);
                    break;
                }
                if (base.value == null || v == n) { //base节点已被删
                    break;
                }
                if ((c = cm(key, n.key)) < 0) { //插入节点大于next节点
                    break out;
                }
                if (c > 0) {
                    base = n;
                    n = f;
                    continue;
                }
                //如果指定了value值
                if (value != null && !value.equals(v)) {
                    break out;
                }
                if (!n.casValue(v, null)) {
                    break;
                }
                if (!n.appendDeleteMarker(f) || !base.casNext(n, f)) {
                    //不停重试删除中的标记和指向下个节点的步骤,通过helpDelete()
                    findNode(key);
                }
                else {
                    //通过unlink()将删除节点的上层索引删除
                    findPredecessor(key);
                    if (head.right == null) {
                        //降级
                        tryReduceLevel();
                    }
                }
                @SuppressWarnings("unchecked")
                V vv = (V) v;
                return vv;
            }
        }
        return null;
    }

    /**
     * 在前三层都为null时降层，有重新检查机制
     */
    private void tryReduceLevel() {
        HeadIndex<K,V> h = head;
        HeadIndex<K,V> d;
        HeadIndex<K,V> e;
        if (h.level > 3 &&
                (d = (HeadIndex<K,V>)h.down) != null &&
                (e = (HeadIndex<K,V>)d.down) != null &&
                e.right == null &&
                d.right == null &&
                h.right == null &&
                casHead(h, d) && // try to set
                h.right != null) // recheck
                casHead(d, h);   // try to backout
    }

    private Node<K, V> findNode(Object key) {
        Objects.requireNonNull(key);
        out:
        for (;;) {
            for (Node<K, V> base = findPredecessor(key), n = base.next; ; ) {
                if (n == null) break out;
                Object v;
                int c;
                Node<K, V> f = n.next;
                if (n != base.next) { //读不一致
                    break;
                }
                if ((v = n.value) == null) { //n节点已被删
                    n.helpDelete(base, f);
                    break;
                }
                if (base.value == null || v == n) { //base节点已被删
                    break;
                }
                if ((c = cm(key, n.key)) == 0) {
                    return n;
                }
                if (c < 0) break out;
                base = n;
                n = n.next;
            }
        }
        return null;
    }


    public V bootomGet(K key) {
        Node first = findFirst();
        assert first != null;
        while (first.next != null) {
            if (cm(key, first.next.key) == 0) {
                @SuppressWarnings("unchecked")
                V vv = (V) first.next.value;
                return vv;
            }
            first = first.next;
        }
        return null;
    }

    private V doGet(Object key) {
        Objects.requireNonNull(key);
        out:
        for (;;) {
            for (Node<K, V> base = findPredecessor(key), n = base.next; ; ) {
                if (n == null) break out;
                Object v;
                int c;
                Node<K, V> f = n.next;
                if (n != base.next) { //读不一致
                    break;
                }
                if ((v = n.value) == null) { //n节点已被删
                    n.helpDelete(base, f);
                    break;
                }
                if (base.value == null || v == n) { //base节点已被删
                    break;
                }
                if ((c = cm(key, n.key)) == 0) { //插入节点大于next节点
                    @SuppressWarnings("unchecked")
                    V vv = (V) n.value;
                    return vv;
                }
                if (c < 0) break out;
                base = n;
                n = n.next;
            }
        }
        return null;
    }

    private V doPut(K key, V value, boolean onlyIfAbsent) {
        Objects.requireNonNull(key);
        Node<K, V> z;//插入的节点
        out:
        for (;;) {
            //通过上层索引找到最底层的节点位置，离插入节点最近的左节点
            for (Node<K, V> base = findPredecessor(key), n = base.next; ; ) {
                if (n != null) {
                    Object v;
                    int c;
                    Node<K, V> f = n.next;
                    if (n != base.next) { //读不一致
                        break;
                    }
                    if ((v = n.value) == null) { //n节点已被删
                        n.helpDelete(base, f);
                        break;
                    }
                    if (base.value == null || v == n) { //base节点已被删
                        break;
                    }
                    if ((c = cm(key, n.key)) > 0) { //插入节点大于next节点
                        base = n;
                        n = n.next;
                        continue;
                    }
                    if (c == 0) { //插入节点等于next节点，替换值
                        if (onlyIfAbsent || n.casValue(v, value)) {
                            @SuppressWarnings("unchecked") V vv = (V) v;
                            return vv;
                        }
                    }
                    //插入节点位于base节点和n节点之间，向下运行
                }
                //插入节点的前继节点找到
                z = new Node<>(key, value, n);
                if (!base.casNext(n, z)) {
                    break;
                }
                break out;
            }
        }
        //建立索引节点，是否建立和索引层高都随机
        int rd = ThreadLocalRandom.current().nextInt();
        if ((rd & 0x80000001) == 0) {//是否建立索引
            int level = 1, max = head.level;
            while (((rd >>>= 1) & 1) != 0) {
                level++;
            }
            Index<K, V> idx = null;
            Index<K, V> header = head;
            int oldLevel = head.level;
            if (level <= max) {
                for (int i = 1; i <= level; i++)
                    idx = new Index<>(z, idx, null);//在插入节点上方建立索引节点
            }
            else {
                level = max + 1;
                @SuppressWarnings("unchecked")
                Index<K, V>[] idxs = (Index<K, V>[]) new Index<?, ?>[level + 1];
                for (int i = 1; i <= level; i++) {
                    idxs[i] = idx = new Index<>(z, idx, null);//在插入节点上方建立索引节点
                }
                for (;;) {//先建新的head
                    header = head;//cas失败重新读值
                    oldLevel = head.level;//cas失败重新读值
                    if (oldLevel >= level) {
                        break;
                    }
                    Node<K, V> oldBase = head.node;
                    HeadIndex<K,V> newHead = head;
                    for(int i = oldLevel + 1; i <= level; i ++) {
                        newHead = new HeadIndex<>(oldBase, newHead, idxs[i], i);
                    }
                    if (casHead(header, newHead)) {
                        header = newHead;
                        idx = idxs[oldLevel];
                        break;
                    }
                }
            }
            Objects.requireNonNull(idx);
            int layer = level;

            while (oldLevel < layer) {
                header = header.down;
                layer--;
            }
            while (layer < oldLevel) {
                header = header.down;
                layer++;
            }
            out:
            for (;;) {//加入每层
                for (Index<K, V> h = header, r = header.right; ; ) {
                    if (r != null) {
                        K rk = r.node.key;
                        Node<K, V> n = r.node;
                        if (n.value == null) {
                            if (!h.unlink(r)) {
                                break;
                            }
                            r = h.right;
                            continue;
                        }
                        if (cm(key, rk) > 0) {
                            h = r;
                            r = r.right;
                            continue;
                        }
                    }
                    if (!(idx.casRight(idx.right, r) && h.casRight(r, idx))) {
                        break;
                    }
                    if (header.down == null) {
                        break out;
                    }
                    header = header.down;
                    idx = idx.down;
                }
            }
        }
        return null;
    }

    private boolean casHead(Index<K,V> header, HeadIndex<K,V> newHead) {
        return UNSAFE.compareAndSwapObject(this, headOffset, header, newHead);
    }

    /**
     * 通过索引落到最下层的基点
     */
    private Node<K, V> findPredecessor(Object key) {
        Objects.requireNonNull(key);
        for (;;) {
            for (Index<K, V> h = head, r = h.right, d; ; ) {
                if (r != null) {
                    K rk = r.node.key;
                    Node<K, V> n = r.node;
                    if (n.value == null) {//right节点被删
                        if (!h.unlink(r))//right节点替换
                            break;
                        r = h.right;//重读right节点
                        continue;
                    }
                    if (cm(key, rk) > 0) {
                        h = r;
                        r = r.right;
                        continue;
                    }
                }
                if ((d = h.down) == null)
                    return h.node;
                h = d;
                r = d.right;
            }
        }
    }

    @SuppressWarnings({"unchecked", "rawtypes"})
    private int cm(Object key, Object rk) {
        return ((Comparable) key).compareTo(rk);
    }

    public void print() {
        Index header = head;
        while (header.down != null) {
            header = header.down;
        }
        Node node = header.node;
        if (node.next != null && node.next.value != null) {
            node = node.next;
        }
        while (node != null && node.value != null) {
            System.out.println(node.key);
            node = node.next;
        }
    }

    public int size() {
        int ret = 0;
        Node<K, V> first = findFirst();
        while (first != null) {
            if (first.getValidValue() != null) {
                ret ++;
            }
            first = first.next;
        }
        return ret;
    }

    static class HeadIndex<K, V> extends Index<K, V> {
        final int level;

        HeadIndex(Node<K, V> node, Index<K, V> down, Index<K, V> right, int level) {
            super(node, down, right);
            this.level = level;
        }
    }

    static class Index<K, V> {
        final Node<K, V> node;
        volatile Index<K, V> down;
        volatile Index<K, V> right;

        Index(Node<K, V> node, Index<K, V> down, Index<K, V> right) {
            this.node = node;
            this.down = down;
            this.right = right;
        }

        private static final sun.misc.Unsafe UNSAFE;
        private static final long rightOffset;

        static {
            try {
                UNSAFE = reflectUnsafe();
                assert UNSAFE != null;
                Class<?> k = Index.class;
                rightOffset = UNSAFE.objectFieldOffset
                        (k.getDeclaredField("right"));
            } catch (Exception e) {
                throw new Error(e);
            }
        }

        boolean casRight(Index<K, V> except, Index<K, V> update) {
            return UNSAFE.compareAndSwapObject(this, rightOffset, except, update);
        }

        final boolean unlink(Index<K, V> r) {
            return node.value != null && casRight(r, r.right);
        }
    }

    static class Node<K, V> {
        final K key;
        volatile Object value;
        volatile Node<K, V> next;

        Node(K key, Object value, Node<K, V> next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }

        Node(Node<K, V> next) {
            this.key = null;
            this.value = this;
            this.next = next;
        }

        private static final sun.misc.Unsafe UNSAFE;
        private static final long valueOffset;
        private static final long nextOffset;

        static {
            try {
                UNSAFE = reflectUnsafe();
                assert UNSAFE != null;
                Class<?> k = Node.class;
                valueOffset = UNSAFE.objectFieldOffset
                        (k.getDeclaredField("value"));
                nextOffset = UNSAFE.objectFieldOffset
                        (k.getDeclaredField("next"));
            } catch (Exception e) {
                throw new Error(e);
            }
        }

        private boolean casNext(Object expect, Object update) {
            return UNSAFE.compareAndSwapObject(this, nextOffset, expect, update);
        }

        private boolean casValue(Object expect, Object update) {
            return UNSAFE.compareAndSwapObject(this, valueOffset, expect, update);
        }

        /**
         * 协助删除
         * 给未添加marker节点的已删除节点添加marker节点
         * 给已有marker节点且后继节点不为null的已删除节点的前驱结点指向后继节点
         */
        private void helpDelete(Node<K, V> base, Node<K, V> f) {
            if (base.next == this && this.next == f) {
                if (f == null || f.value != f) {
                    appendDeleteMarker(f);
                } else {
                    base.casNext(this, f.next);
                }
            }
        }

        boolean appendDeleteMarker(Node<K, V> f) {
            return casNext(f, new Node<>(f));
        }

        V getValidValue() {
            Object v = value;
            if (v == this || v == BASE_HEADER)
                return null;
            @SuppressWarnings("unchecked")
            V vv = (V)v;
            return vv;
        }
    }

    public static Unsafe reflectUnsafe() {
        try {
            Field field = Unsafe.class.getDeclaredField("theUnsafe");
            field.setAccessible(true);
            return (Unsafe) field.get(null);
        } catch (NoSuchFieldException | IllegalAccessException e) {
            e.printStackTrace();
        }
        return null;
    }

    private static final sun.misc.Unsafe UNSAFE;
    private static final long headOffset;
    static {
        try {
            UNSAFE = reflectUnsafe();
            Class<?> k = MiniSkipListMap.class;
            assert UNSAFE != null;
            headOffset = UNSAFE.objectFieldOffset
                    (k.getDeclaredField("head"));
        } catch (Exception e) {
            throw new Error(e);
        }
    }

}
